package Leetcode.Stack;

import java.util.Stack;

public class InfixToPostfix {

    // 检查字符是否是操作符
    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')';
    }

    // 检查字符是否是数字
    private static boolean isNumber(char ch) {
        return ch >= '0' && ch <= '9';
    }

    // 检查字符是否是左括号
    private static boolean isLeftBracket(char ch) {
        return ch == '(';
    }

    // 检查字符是否是右括号
    private static boolean isRightBracket(char ch) {
        return ch == ')';
    }

    // 比较操作符的优先级
    private static int compareOperatorPriority(char op1, char op2) {
        if (op1 == '(' || op1 == ')') {
            return 1;
        }
        if (op2 == '(' || op2 == ')') {
            return -1;
        }
        int op1Priority = getOperatorPriority(op1);
        int op2Priority = getOperatorPriority(op2);
        return op1Priority - op2Priority;
    }

    // 获取操作符的优先级
    private static int getOperatorPriority(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }

    /**
     初始化一个空的后缀表达式字符串和一个操作符栈。
     遍历中缀表达式的每个字符：
     如果字符是数字，将其添加到后缀表达式字符串中。
     如果字符是操作符或括号：
     如果操作符栈为空或栈顶操作符为左括号 (，将当前操作符压入栈中。
     否则，如果当前操作符优先级高于栈顶操作符，将栈顶操作符弹出并添加到后缀表达式字符串中，然后将当前操作符压入栈中。
     如果当前操作符优先级低于或等于栈顶操作符，将栈顶操作符弹出并添加到后缀表达式字符串中，直到当前操作符优先级高于栈顶操作符，然后将当前操作符压入栈中。
     如果字符是左括号 (，将其压入操作符栈中。
     如果字符是右括号 )，则不断将栈顶操作符弹出并添加到后缀表达式字符串中，直到遇到左括号 (，然后将左括号弹出栈。
     遍历结束后，将操作符栈中剩余的操作符弹出并添加到后缀表达式字符串中。

     下面代码有点问题
     * @param infixExpression 中缀
     * @return  后缀
     */
    public static String infixToPostfix(String infixExpression) {
        Stack<Character> stack = new Stack<>();
        StringBuilder postfixExpression = new StringBuilder();

        for (int i = 0; i < infixExpression.length(); i++) {
            char ch = infixExpression.charAt(i);

            if (isNumber(ch)) {
                postfixExpression.append(ch);
            } else if (isOperator(ch)) {
                while (!stack.isEmpty()
                        && !isLeftBracket(stack.peek())
                        && compareOperatorPriority(stack.peek(), ch) >= 0) {
                    postfixExpression.append(stack.pop());
                }
                stack.push(ch);
            } else if (isLeftBracket(ch)) {
                stack.push(ch);
            } else if (isRightBracket(ch)) {
                while (!stack.isEmpty() && !isLeftBracket(stack.peek())) {
                    postfixExpression.append(stack.pop());
                }
                stack.pop(); // 弹出左括号
            }
        }

        while (!stack.isEmpty()) {
            postfixExpression.append(stack.pop());
        }

        return postfixExpression
//                .reverse()
                .toString();
    }
    /**
     * 美团
     * 将中缀表达式转换为后缀表达式
     * @param s 中缀表达式
     * @return String字符串 后缀表达式
     */
    private static String postfix(String s){
        // 后缀表达式
        StringBuilder sb = new StringBuilder();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        while(i < s.length()){
            char c = s.charAt(i++);
            if (c == '(' || c == '+' || c == '-' || c == '*'){
                // 加一个空格是为了将操作数之间隔开
                sb.append(" ");
                pushOP(sb,c,ops);
                continue;
            }
            if (c == ')'){
                // 弹出操作符直到(
                while(ops.peek() != '('){
                    sb.append(ops.pop());
                }
                ops.pop();
                continue;
            }
            sb.append(c);
        }
        // 弹出栈中元素
        while(!ops.isEmpty()){
            sb.append(ops.pop());
        }
        return sb.toString();
    }
    private static void pushOP(StringBuilder sb,char op,Stack<Character> ops){
        // 栈空，或者栈顶元素为(,操作符直接放入栈中
        if (ops.isEmpty() || ops.peek() == '(' || op == '('){
            ops.add(op);
            return;
        }
        char c = ops.peek();
        // 栈顶操作符的优先级低于当前操作符，直接压入栈中
        if (c != '*' && op == '*'){
            ops.add(op);
            return;
        }
        // 否则，弹出栈顶元素，继续比较
        c = ops.pop();
        sb.append(c);
        pushOP(sb,op,ops);
    }

    public static void main(String[] args) {
//        String infixExpression = "3 + 5 * (9 - 4) / 2";
        String infixExpression = "(2*(3-4))*5";
        String postfixExpression = postfix(infixExpression);
        System.out.println("后缀表达式为： " + postfixExpression);
    }
}
